import entity.TreeNode;

import java.util.HashMap;

public class ConstructBTreeFromPreAndInOrder {
    /*
    * 105. 从前序与中序遍历序列构造二叉树
    * 给定两个整数数组 preorder 和 inorder ，
    * 其中 preorder 是二叉树的先序遍历，
    *  inorder 是同一棵树的中序遍历，
    * 请构造二叉树并返回其根节点。
    *
    * 1 <= inorder.length <= 3000
    * postorder.length == inorder.length
    * -3000 <= inorder[i], postorder[i] <= 3000
    * inorder 和 preorder 都由 不同 的值组成
    * preorder 中每一个值都在 inorder 中
    * inorder 保证是树的中序遍历
    * preorder 保证是树的先序遍历
    * */
    public static void main(String[] args){
    }

    // 我的想法：写了106，这回该会写105了吧, 和106一样，
    // 就是把后序换成先序了，之前是取最后一个值，现在是取第一个值

    //还是用一个map存下索引值，避免每次递归都遍历
    HashMap<Integer, Integer> map = new HashMap<>();
    public TreeNode mySolution(int[] preorder, int[] inorder){
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    // 1.当然需要返回节点用于构造树， 传入两个数组，以及截取的索引(左闭右开)
    private TreeNode build(int[] preorder, int preStart, int preEnd,
                           int[] inorder, int inStart, int inEnd){
        if(inStart >= inEnd)    // 没有值了
            return null;
        TreeNode root = new TreeNode(preorder[preStart]);
        if(inEnd - inStart == 1)    // 叶子节点
            return root;
        // 开始裁剪
        int index = map.get(root.val);
        int cut = preStart + 1 + (index - inStart);
        root.left = build(preorder, preStart+1, cut, inorder, inStart, index);
        root.right = build(preorder, cut, preEnd, inorder, index+1, inEnd);
        return root;
    }
}
